package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 1870. 准时到达的列车最小时速
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/16 20:22
 */
public class MinSpeedOnTime {


    public static void main(String[] args) {
        MinSpeedOnTime test = new MinSpeedOnTime();

        // 1
//        int[] dist = {1,3,2};
//        double hour = 6;

        // 20
        int[] dist = {1,3,2};
        double hour = 2.1;

        // 3
//        int[] dist = {1,3,2};
//        double hour = 2.7;

        int i = test.minSpeedOnTime(dist, hour);
        System.out.println(i);
    }

    private int[] dist;
    private int length;

    public int minSpeedOnTime(int[] dist, double hour) {
        length = dist.length - 1;
        if (length >= hour) {
            return -1;
        }
        this.dist = dist;
        int end = Integer.MAX_VALUE;
        int st = 1;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            double v = find(m);
            if (v > hour) {
                st = m + 1;
            } else {
                end = m;
            }
        }
        return st;
    }

    private double find (int v) {
        int sum = 0;
        int c = v - 1;
        for (int i = 0; i < length; i++) {
            sum += (dist[i] + c) / v;
        }
        return sum + (double)dist[length] / v;
    }

}
